package com.yvon.service.demo.algorithm.offer;

import com.yvon.service.demo.algorithm.offer.ext.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 序列化二叉树
 * 请实现两个函数，分别用来序列化和反序列化二叉树。
 */
public class P37 {

    public static void main(String[] args) {
        Codec codec = new P37().new Codec();
        TreeNode nod1 = new TreeNode(3);
        TreeNode nod2 = new TreeNode(9);
        TreeNode nod3 = new TreeNode(20);
        TreeNode nod4 = new TreeNode(8);
        TreeNode nod5 = new TreeNode(6);
        TreeNode nod6 = new TreeNode(15);
        TreeNode nod7 = new TreeNode(7);
        TreeNode nod8 = new TreeNode(90);
        TreeNode nod9 = new TreeNode(67);
        nod1.left = nod2;
        nod1.right = nod3;
        nod2.left = nod4;
        nod2.right = nod5;
        nod3.left = nod6;
        nod3.right = nod7;
        nod6.left = nod8;
        nod6.right = nod9;
        TreeNode.prePrint(nod1);
        System.out.println();
        String serialize = codec.serialize(nod1);
        System.out.println(serialize);
        TreeNode deserialize = codec.deserialize(serialize);
        System.out.println();
        TreeNode.prePrint(deserialize);
    }

    class Codec {
        public String serialize(TreeNode root) {
            if (root == null) {
                return "";
            }
            StringBuilder sb = new StringBuilder();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                if (node != null) {
                    sb.append(node.value + ",");
                    queue.offer(node.left);
                    queue.offer(node.right);
                }else {
                    sb.append("null,");
                }
            }
            return sb.toString();
        }

        public TreeNode  deserialize(String data) {
            if (data == null || data.length() == 0) {
                return null;
            }
            String[] split = data.split(",");
            Queue<TreeNode> queue = new LinkedList<>();
            TreeNode root = new TreeNode(Integer.parseInt(split[0]));
            queue.offer(root);
            int i = 1;
            while (!queue.isEmpty() && i < split.length) {
                TreeNode node = queue.poll();
                if (!"null".equals(split[i])) {
                    node.left = new TreeNode(Integer.parseInt(split[i]));
                    queue.offer(node.left);
                }
                i++;
                if (!"null".equals(split[i])) {
                    node.right = new TreeNode(Integer.parseInt(split[i]));
                    queue.offer(node.right);
                }
                i++;
            }
            return root;
        }
    }
}
